1. Field of the Invention
This invention relates to the field of computer software and more specifically to the efficient and reliable multicasting of information in a network environment. Portions of this patent document may contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
Sun, Sun Microsystems, the Sun logo, Solaris, xe2x80x9cWrite Once, Run Anywherexe2x80x9d, Java, JavaOS, JavaStation and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are used under license and are trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.
2. Background Art
Computer networks, especially the Internet, are used to propagate information to multitudes of users. Sometimes, the Internet is used to broadcast identical information from a network node (i.e. a xe2x80x9cserverxe2x80x9d or a xe2x80x9csenderxe2x80x9d) to many network endpoints (i.e., xe2x80x9cclientsxe2x80x9d or xe2x80x9creceiversxe2x80x9d). This is known as xe2x80x9cmulticasting.xe2x80x9d Examples of multicasting include the broadcasting of video and/or audio information of a lecture in one classroom to many other classrooms, or the broadcast of current stock market figures from a main source (e.g., a Bloomberg market news server) to numerous Internet news web sites (e.g., CNN, MSNBC, etc.).
FIG. 6 is a block diagram of a multicast environment, illustrating a sender and multiple receivers. Identical messages can be sent from sender 610 to receivers 620 through 680 as members of one multicast group. Alternatively, receivers 620 and 630 can form one multicast group, while receivers 640 through 660, and 670 through 680 form additional multicast groups.
Current methods for multicasting are designed to enable the multicasting of information to thousands of receivers. However, most actual uses for multicasting are only to a relatively small number of users, and therefore most prior art schemes do not work well for most multicasting situations.
The above referenced problems can be understood from a review of a general description of a network environment, including the Internet, communication protocols, and the current multicasting schemes.
In modern computing environments, it is common to employ multiple computers or workstations linked together in a network to communicate between, and share data with, network users. A network also may include resources, such as printers, modems, file servers, etc., and may also include services, such as electronic mail, broadcasting or multicasting services. A resource can, for example, simultaneously provide or transmit information to a plurality of users as requested.
A network can be a small system that is physically connected by cables or via wireless communication (a local area network or xe2x80x9cLANxe2x80x9d). Alternatively, several separate networks can be connected together to form a larger network (a wide area network or xe2x80x9cWANxe2x80x9d). Other types of networks include the Internet, telcom networks, Intranet, extranets, wireless networks, and other networks over which electronic, digital and/or analog data may be communicated.
The Internet is a client/server system that includes a worldwide network of interconnected computers. A xe2x80x9cclientxe2x80x9d is the computer that is used to access the Internet. An Internet client accesses a computer on the network (xe2x80x9cserverxe2x80x9d) via an Internet provider. An Internet provider is an organization that provides a client with access to the Internet (via analog telephone line or Integrated Services Digital Network line, for example). Typically, when a user logs onto the Internet or the World Wide Web (WWW), using a client computer, the user views xe2x80x9cweb pagesxe2x80x9d that are stored on a remote server. Information including data files, and the web pages are often transferred between the client and the server.
A client can, for example, download a file from or send an electronic mail message to another computer/client using the Internet. A client may also participate in a multicast session, for example, to tune into a radio show transmitted via the Internet. The server or the client may have to evaluate the type of data transferred (e.g., text, audio, video, etc.) prior to processing the data. One method of data transmission may be more efficient than another method depending on the type of data being transferred, and/or the number of users the data is intended for.
Information servers maintain information that are transferable through the WWW and are capable of processing a client request to access that information. Information servers can implement a multicast session for transmittal of identical information to a group of clients. To enable the computers on a network to communicate with each other, a set of standardized rules for exchanging the information between the computers, referred to as a xe2x80x9cprotocolxe2x80x9d is utilized.
Communication protocols generally specify the data format, timing, sequencing, and error checking of data transmissions. Various communication protocols are used in the networking environment. For example, one communication protocol is referred to as the transmission control protocol/Internet protocol (xe2x80x9cTCP/IPxe2x80x9d). The TCP/IP communication protocol includes a set of communication protocols used on the Internet and on many multiplatform networks.
The TCP/IP protocol family is made up of numerous individual protocols (e.g., file transfer protocol (xe2x80x9cFTPxe2x80x9d), transmission control protocol (xe2x80x9cTCPxe2x80x9d), and network terminal protocol (xe2x80x9cTELNETxe2x80x9d)). The TCP protocol is responsible for breaking up a message to be transmitted and including it in packets of manageable size, reassembling the message at the receiving end, resubmitting any packets that get lost (i.e., are not delivered), and reordering the data included in the packets in the appropriate format. A xe2x80x9cpacketxe2x80x9d is an encapsulated form of data or information (also referred to as a xe2x80x9cdatagramxe2x80x9d) that is transferred or passed across the Internet according to the communication protocol standards. A packet contains a source and destination address along with the information intended for transmission.
The TCP transfer protocol is often utilized to transmit large amounts of information because of its ability to break up information into packets and to reassemble the information at the receiving end. Other communication protocols (e.g., multicasting protocols) manage other functional aspects of information communication, and thus operate on a higher level than the TCP/IP protocol. These higher level protocols utilize TCP/IP as the underlying means for communication of information.
To transfer information, a higher level protocol defines a set of commands that one machine sends to another (e.g., commands to specify who the sender of the message is, who it is being sent to, and the text of the message) encapsulated in a series of packets encoded according to the specifications of that communication protocol. Those packets in turn are broken up, as needed, and encapsulated in TCP/IP packets so that they are transmitted to a destination on the network, via the TCP/IP protocol.
A communication protocol that runs on top of the TCP/IP and is utilized to control the multicast of media information is the Real Time Transport Protocol (xe2x80x9cRTPxe2x80x9d). RTP is used to transmit packets of audio and video information on a network. An RTP packet is a data packet consisting of a header, a list of sources, and the information intended for transmission. Typically, a single RTP packet is contained in one packet of the underlying protocol (e.g., TCP/IP). Therefore, the rate of transfer of audio/video information is at least equal to the rate of transmission of TCP/IP packets.
Multicasting of information from a source to a number of receivers takes place during an established RTP session. For each receiver, the session is established via a particular set of destination addresses, for example, a network address and a port address for RTP. A port is an abstraction that protocols use to distinguish among multiple destinations within a given host computer. As such, the destination address may be common for all receivers, for example, as in the case of transmission to a group of receivers in the same network. Alternatively, each receiver may have a different destination address, for example, as in the case of individual transmissions to receivers located on multiple networks.
One common problem associated with data transmission on a network is data loss. For example, the Internet, like other packet networks, occasionally loses and orders the retransmission of lost data packets. To cope with these impairments, an RTP packet contains a sequence number that allows the receivers to detect out of sequence packets and reorder the packets that have not been delivered.
Various schemes have been implemented to reduce the number of packet losses and to enhance the transmission rate of media data in a multicasting environment. For a better understanding of the invention and its advantages, a brief summary of the current multicasting techniques and the problems associated with them is included below.
Data transport via the RTP may be augmented by a control protocol (RTCP) to allow monitoring of the data-loss in a manner scaleable to large multicast networks, and to provide minimal control and identification functionality. One existing technique known to the inventors for enhancing the speed and efficiency of information transport is the RTCP.
The RTP control protocol (RTCP) is based on the periodic transmission of control packets to all receivers in an RTP session. A control packet (RTCP packet) includes information relating to the successful delivery of data packets (i.e., indicating which packets have been received successfully, or those that have been lost during transmission). Thus, RTCP""s primary function is to provide feedback or a response on the quality of the data distribution via the RTP.
The feedback may be directly useful for controlling the flow of data and data congestion in a network. Responses generated by the receivers are compiled into a comprehensive report sent to all receivers. The report is used to diagnose and repair faults in data delivery. For example, based on the report the rate of data distribution may be enhanced by updating a receiver""s response rate and determining whether data delivery problems are directed to a group of receivers or if they are global.
The transmission of responses creates network traffic (i.e., xe2x80x9ccontrol trafficxe2x80x9d) in addition to the normal network traffic associated with data transmission. As a result, control traffic grows linearly with the number of receivers in a multicast session. RTP is designed to allow the multicast of information to audiences of various sizes ranging from a few to tens of thousands. Therefore, to avoid congesting the network traffic by a large volume of control data that are transported via the RTCP packets, the receiver""s response rate must be controlled.
For each multicast session, it is assumed that the data traffic is subject to an aggregate limit called the xe2x80x9csession bandwidthxe2x80x9d to be divided among all the receivers. Bandwidth is a measure in data communications that signifies the maximum data transmission capacity during a communication session. Typically, a session bandwidth is limited as enforced by the network. Control traffic associated with the transmission of RTCP packets is limited to a small and known fraction of the session bandwidth, so that the primary function of the transport protocol (i.e. transport of media data) is not impaired.
To ensure the reliability and accuracy of information communicated from a sender to a receiver, lost information packets must be retransmitted by a sender to the intended receivers. Typically, transported information is embedded in identifiable communication packets, so that a receiver can detect information packets that are out of sequence. When a receiver detects that a series of received packets are out of sequence, the receiver can request the sender to resubmit any missing packets.
One information recovery scheme is referred to as xe2x80x9clocal repairxe2x80x9d. In this scheme, a receiver does not forward a request to the sender for retransmission of lost packets. Instead, it queries a local receiver to determine whether that receiver has received the missing packet, and requests the delivery of that packet from the queried receiver.
For example, in a multicast environment, receivers can be grouped together based on certain shared characteristic, (e.g., a number of receivers may be members of the same network, or a number of receivers may be grouped together based on geographic location, or their data communication attributes) forming a multicast group. If for any reason one of the receivers in a group does not receive an information packet broadcasted to the multicast group, then instead of contacting the sender it can request a receiver within the group for the undelivered packet.
Referring to FIG. 6, for example, receivers 620 and 630 are in one multicast group and therefore receive identical packets of information at the same time. Thus, receivers 620 and 630 are considered local to one another. In a local repair scheme, if for example receiver 620 does not receive a packet, it requests local receiver 630 for a copy of the lost packet, instead of asking server 610 to retransmit that packet.
A problem with the local repair multicasting scheme is that information transmitted by a local receiver may not be as reliable as information provided by the sender. There is a chance that transmitted information from a local receiver may be corrupted or altered for various reasons. Consider for example two broadcasting stations that rely on the Bloomberg news network for the latest stock market information. If the two stations are in competition with each other, it would be undesirable for one to rely on the other for retransmission of any information, especially information as critical and vital as stock market figures.
Using the local repair scheme, a requesting receiver is unable to verify the authenticity and accuracy of information it receives from a local receiver. Thus, more secure error recovery methods are needed that can be used in a multicast environment.
Some current multicasting schemes are implemented so that a sender may adjust the flow and frequency of control traffic generated by the receivers. In this multicasting scheme, the sender polls each receiver for feedback. For example, a sender may from time to time send a polling message to all or a group of receivers requesting a response including data-loss information. This scheme relies on the responses received from the polled receivers for retransmitting any undelivered or lost packets. The sender analyzes the responses and determines which packets should be resubmitted. The missing information packets are then retransmitted based on a predetermined policy.
FIG. 7 is a block diagram illustrating data streams 1 through 3, each comprising data and/or control packets. Data stream 1 is an example of a communication stream that is comprised of data packets only. It is representative of an environment where no control information is transported. Thus, the entire communication bandwidth is dedicated to transmission of data.
Data stream 2 is an example of a communication stream comprised of both data packets and control information. The control information can be generated, for example, in a polling scheme both by the sender in form of polling messages, and also by the receivers in form of responses to the polling messages. The combination of this messages and responses creates control traffic that is in addition to the normal data traffic. This control traffic uses up a portion of the transmission bandwidth. Since the transmission bandwidth is finite, as control traffic increases the bandwidth available for transmission of data decreases.
Consequently, use of the prior art polling scheme is undesirable when a significant number of receivers are participating in the polling process. As the number of receivers polled increases, so does the control traffic bandwidth associated with transmittal of polling requests, and responses. Hence, in a large multicast group a substantial range of the network""s transmission bandwidth is consumed by control traffic. Data stream 3 illustrates how a substantial amount of control traffic can effectively reduce the available bandwidth for the transmission of data, and thereby diminish transmission efficiency. For example, in comparison with data stream 1, the data transmission rate in data stream 3 can at times be diminished by two thirds.
The aforesaid prior art schemes for data-loss recovery in a multicasting environment are inefficient and expensive as too much overhead is associated with error detection and fault tolerance functions and processes implemented therein. The above-referenced shortcomings effect the timely delivery of information in a network, and lead to additional failure states in data delivery.
Further, as these schemes are designed for multicasting of information to large audiences, they can be complex and can contain many lines of code. Thus, verifying the proper operation and maximizing the performance of these methods are burdensome"" and render such methods unreliable, even when involving a relatively small audience. As such, simpler methods and solutions are needed to provide for more reliable and efficient multicasting, particularly in cases where the number of participants in the multicast group is not substantially large.
A method and apparatus for efficient and reliable multicasting in a network environment is provided. In embodiments of the invention, a sender transmits identical information encapsulated in data packets to a plurality of receivers participating in a multicast session. Periodically, receivers submit responses that include xe2x80x9ccontrol dataxe2x80x9d regarding the loss or receipt of data packets transmitted by the sender. Using this information a sender retransmits any undelivered packets to intended receivers.
In embodiments of the invention, data loss reports are accumulated and are submitted at predetermined but adjustable time intervals to minimize the number of responses and therefore the amount of control information generated at each time interval by each receiver. Further, responses are automatically generated by receivers at fixed and tunable time intervals without any polling from the sender. This also eliminates the need for dedication of a portion of the network bandwidth to control information associated with the polling requests.
In embodiments of the invention, packet loss responses are generated at time intervals that are adjustable based on the performance of the receivers. A time interval in generation of packet loss information may result in a lower error correction rate. However, since the control traffic that results from the generation of the responses is monitored, the failure states associated with an over congested network bandwidth are minimized. Therefore, the multicasting takes place at a more reliable and predictable rate.